#!/usr/bin/python
#
# exp.py - Classes to represent underlying data structures for the grammar
#	 below, for the mini-compiler.
#
# Kurt Schmidt
# 8/07
#
# DESCRIPTION:
#		Just a translation of the C++ implementation by Jeremy Johnson (see
#		programext.cpp)
#
# EDITOR: cols=80, tabstop=2
#
# NOTES
#	environment:
#		a dict
#
#		Procedure calls get their own environment, can not modify enclosing env
#
#	Grammar:
#		program: stmt_list 
#		stmt_list:  stmt ';' stmt_list 
#		    |   stmt  
#		stmt:  assign_stmt 
#		    |  define_stmt 
#		    |  if_stmt 
#		    |  while_stmt 
#		assign_stmt: IDENT ASSIGNOP expr
#		define_stmt: DEFINE IDENT PROC '(' param_list ')' stmt_list END
#		if_stmt: IF expr THEN stmt_list ELSE stmt_list FI
#		while_stmt: WHILE expr DO stmt_list OD
#		param_list: IDENT ',' param_list 
#		    |      IDENT 
#		expr: expr '+' term   
#		    | expr '-' term   
#		    | term            
#		term: term '*' factor   
#		    | factor            
#		factor:     '(' expr ')'  
#		    |       NUMBER 
#		    |       IDENT 
#		    |       funcall 
#		funcall:  IDENT '(' expr_list ')'
#		expr_list: expr ',' expr_list 
#		    |      expr 
#

import sys

####  CONSTANTS   ################

	# the variable name used to store a proc's return value
returnSymbol = 'return'

tabstop = '  ' # 2 spaces

######   CLASSES   ##################

class Expr :
        '''Virtual base class for expressions in the language'''

        def __init__( self ) :
                raise NotImplementedError(
                        'Expr: pure virtual base class.  Do not instantiate' )

        def eval( self, nt, ft, ht ) :
                '''Given an environment and a function table, evaluates the expression,
                returns the value of the expression (an int in this grammar)'''
                print "in Expr"
                raise NotImplementedError(
                        'Expr.eval: virtual method.  Must be overridden.' )

        def display( self, nt, ft, depth=0 ) :
                'For debugging.'
                raise NotImplementedError(
                        'Expr.display: virtual method.  Must be overridden.' )



class NtEntry :
	
	def __init__(self,element,isList) :
		self.element = element
		self.isList = isList
	
	def eval(self, nt,ft,ht) :
		return self

class HeapCell:

	def __init__(self,con,cdr,isPtr) :
		self.con = con
		self.cdr = cdr
		self.isPtr = isPtr
		self.mark = 0	

class Heap :

	def __init__(self) :
		self.mem = range(8)
		for i in range(len(self.mem)) :
			self.mem[i] = HeapCell(0,i+1,0)
	
		self.mem[len(self.mem)-1].cdr = -1
		self.available = 0

	def add_el_to_list(self,con,cdr,isPtr,nt) :
		if( self.available == -1 ) :
			self.mark_and_sweep(nt)
		
		if( self.available == -1 ) :
			print " memory is full"
			sys.exit(0)
			
		if(cdr.isList == 1) :
			if(cdr.element == -1) :
				index = self.available
				self.available = self.mem[self.available].cdr
				self.mem[index] = HeapCell(con.element,-1,con.isList)
		
			else :
				index = self.available
	                        self.available = self.mem[self.available].cdr
        	                self.mem[index] = HeapCell(con.element,cdr.element,con.isList)

                else :
			print "Syntax error : second parameter has to be a list"
		

		return NtEntry(index,1)
	
	def isEnd(self,addr) :
		'if the addres is end return 1 else 0'
		if(self.mem[addr].cdr == -1) :
			return 1
		else :
			return 0
	
	
	def listPrinter(self,entry) :
		addr = entry.element
		return "[" + self.printer(addr) + "]"

	def printer(self, addr):
		output = ""
		if(self.isList(addr)):
			output = "[" + self.printer(self.getCon(addr)) + "]"
		else :
			output = str(self.getCon(addr))
		
		if(self.isEnd(addr) == 0) :
			output = output +","+ self.printer(self.getCdr(addr))
	
		return output

	
	def getCdr(self,addr) :
		return self.mem[addr].cdr

	def getCon(self,addr) :
		return self.mem[addr].con

	def isList(self,addr) :
		if(self.mem[int(addr)].isPtr == 1):
			return 1
		else :
			return 0	
	
	def mark(self,addr) :
		if(addr != -1) :
			print" marked" + str(addr)
			self.mem[addr].mark = 1
			self.mark(self.getCdr(addr))
			if(self.isList(addr) == 1) :
				self.mark(self.getCon(addr))
		
			

	def sweep(self,addr) :
		self.mem[addr].con = 0
		self.mem[addr].cdr = self.available
		self.available = addr

	def mark_and_sweep(self,nt) :
		for k in nt :
                       if(nt[k].isList ==1) :
				self.mark(nt[k].element)

	
		for m in range(len(self.mem)) :
			if(self.mem[m].mark == 0) :
				self.sweep(m)
			else :
				self.mem[m].mark = 0
	

class Number( Expr ) :
	'''Just integers'''

	def __init__( self, v=0 ) :
		self.value = v
		self.isList = 0	
	def eval( self, nt, ft, ht ) :
		return NtEntry(self.value,0) 

	def display( self, nt, ft, depth=0 ) :
		print "%s%i" % (tabstop*depth, self.value)

class Ident( Expr ) :
	'''Stores the symbol'''

	def __init__( self, name ) :
		self.name = name
	
	def eval( self, nt, ft, ht ) :
		return nt[ self.name ]

	def display( self, nt, ft, depth=0 ) :
		print "%s%s" % (tabstop*depth, self.name)


class Times( Expr ) :
	'''expression for binary multiplication'''

	def __init__( self, lhs, rhs ) :
		'''lhs, rhs are Expr's, the operands'''
		self.isList = "0"

		# test type here?
		# if type( lhs ) == type( Expr ) :
		self.lhs = lhs
		self.rhs = rhs
	
	def eval( self, nt, ft, ht ) :
		return self.lhs.eval( nt, ft, ht ) * self.rhs.eval( nt, ft, ht )

	def display( self, nt, ft, depth=0 ) :
		print "%sMULT" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class Plus( Expr ) :
	'''expression for binary addition'''

	def __init__( self, lhs, rhs ) :
		self.lhs = lhs
		self.rhs = rhs
		self.isList = "0"
	
	def eval( self, nt, ft, ht ) :
		return self.lhs.eval( nt, ft, ht ) + self.rhs.eval( nt, ft, ht )

	def display( self, nt, ft, depth=0 ) :
		print "%sADD" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class Minus( Expr ) :
	'''expression for binary subtraction'''

	def __init__( self, lhs, rhs ) :
		self.lhs = lhs
		self.rhs = rhs
		self.isList = "0"
	
	def eval( self, nt, ft, ht ) :
		return self.lhs.eval( nt, ft, ht ) - self.rhs.eval( nt, ft, ht )

	def display( self, nt, ft, depth=0 ) :
		print "%sSUB" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class Cons( Expr ) :
	'''adds the listelement to the beginning of the given list'''

	def __init__( self, listelement, list ) :
		self.listelement = listelement
		self.list = list
	
		
	
	def eval( self, nt, ft, ht) :
		return ht.add_el_to_list(self.listelement.eval(nt,ft,ht),self.list.eval(nt,ft,ht),self.listelement.isList,nt)


	def display( self, nt, ft, depth=0 ) :
		print "%sCONS" % (tabstop*depth)
		self.listelement.display( nt, ft, depth+1 )
		self.list.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))



class Car(Expr) :
	'''returns the first element in the list'''

	def __init__(self,list) :
		self.list = list
		self.isList = "0"

	def eval(self,nt,ft,ht) :
		return

class Nullp( Expr ) :
	'''return 1 if givien list is Null 0 otherwise'''

	def __init__( self, list ) :
		self.list = list
		self.isList = "1"
		
	
	def eval( self, nt, ft, ht) :
		self.list = self.list.eval(nt,ft,ht)
		self.list.insert(0,self.listelement)
		return "0"

	def display( self, nt, ft, depth=0 ) :
		print "%sNULL" % (tabstop*depth)
		self.list.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))

class Intp( Expr ) :
	'''return 1 if givien expression is integer 0 otherwise'''

	def __init__( self, number ) :
		self.number = number
		
	
	def eval( self, nt, ft, ht) :
		if self.number.eval(nt, ft, ht).isList == true:
			return "0"
		else:
			return "1"
		

	def display( self, nt, ft, depth=0 ) :
		print "%sINTP" % (tabstop*depth)
		#self.number.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))

class Listp(Expr) :
	'''returns 1 if the expr is a list'''

	def __init__(self,expr) :
		self.expr = expr
		

	def eval(self,nt,ft,ht) :
		if(self.expr.eval(nt,ft,ht).isList == true) :
			return 1
		else : 
			return 0

	def display( self, nt, ft, depth=0 ) :
		print "%sLISTP" % (tabstop*depth)
		self.listelement.display( nt, ft, depth+1 )
		self.list.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))

class FunCall( Expr ) :
	'''stores a function call:
	  - its name, and arguments'''
	
	def __init__( self, name, argList ) :
		self.name = name
		self.argList = argList
		self.isList = "0"
	
	def eval( self, nt, ft, ht ) :
		print "in FunCall"
		return ft[ self.name ].apply( nt, ft, ht, self.argList )

	def display( self, nt, ft, depth=0 ) :
		print "%sFunction Call: %s, args:" % (tabstop*depth, self.name)
		for e in self.argList :
			e.display( nt, ft, depth+1 )


class List( Expr) :
	'''List'''

	def __init__(self,seq = []) :
		self.seq = seq
		self.isList = 1
	
	def insert(self,listelement) :
		self.seq.insert(listelement)

	def eval(self, nt ,ft, ht) :
		return NtEntry( self.seq.eval(nt,ft,ht).element,self.isList)
	
	def myPrint(self,nt,ft,ht) :
		return ht.printer(self.seq)

	def display( self, nt, ft, depth = 0) :
		print "%sLIST[" % (tabstop*depth)
		self.seq.display(nt,ft,depth+1)
		print "%s]" % (tabstop*depth)


class Sequence(Expr) :
	'''Sequence'''

	def __init__(self) :
		self.seq = NtEntry(-1,1)
		self.isList = 1
		self.listelement = 0
	
	def insert(self, listelement) :
		self.seq = Cons(listelement, self.seq)	
		
	def eval(self,nt,ft,ht) : 
		
		return self.seq.eval(nt,ft,ht)

	def display( self, nt , ft, depth = 0) :
		print "%sSEQUENCE " % (tabstop*depth)
		

           



class Listelement(Expr) :
	''' Listelement '''

	def __init__(self, element) :
		self.element = element
		self.isList = element.isList

	def eval(self,nt,ft, ht) :
		return self.element.eval(nt,ft,ht)
	
	def display( self, nt, ft, depth = 0) :
		print "%s" % (tabstop*depth)
		self.element.display(nt,ft,depth+1)

#-------------------------------------------------------

class Stmt :
	'''Virtual base class for statements in the language'''

	def __init__( self ) :
		raise NotImplementedError(
			'Stmt: pure virtual base class.  Do not instantiate' )

	def eval( self, nt, ft, ht ) :
		'''Given an environment and a function table, evaluates the expression,
		returns the value of the expression (an int in this grammar)'''

		raise NotImplementedError(
			'Stmt.eval: virtual method.  Must be overridden.' )

	def display( self, nt, ft, depth=0 ) :
		'For debugging.'
		raise NotImplementedError(
			'Stmt.display: virtual method.  Must be overridden.' )


class AssignStmt( Stmt ) :
	'''adds/modifies symbol in the current context'''

	def __init__( self, name, rhs ) :
		'''stores the symbol for the l-val, and the expressions which is the
		rhs'''
		self.name = name
		self.rhs = rhs
		
	def eval( self, nt, ft, ht ) :
		


		nt[self.name] = self.rhs.eval(nt,ft,ht)
		print "In AssignStmt"

	def display( self, nt, ft, depth=0 ) :
		print "%sAssign: %s :=" % (tabstop*depth, self.name)
		self.rhs.display( nt, ft, depth+1 )


class DefineStmt( Stmt ) :
	'''Binds a proc object to a name'''

	def __init__( self, name, proc ) :
		self.name = name
		self.proc = proc
		self.isList = "0"

	def eval( self, nt, ft, ht ) :
		print "in DefineStmt"
		ft[ self.name ] = self.proc

	def display( self, nt, ft, depth=0 ) :
		print "%sDEFINE %s :" % (tabstop*depth, self.name)
		self.proc.display( nt, ft, depth+1 )


class IfStmt( Stmt ) :

	def __init__( self, cond, tBody, fBody ) :
		'''expects:
		cond - expression (integer)
		tBody - StmtList
		fBody - StmtList'''
		
		self.cond = cond
		self.tBody = tBody
		self.fBody = fBody
		self.isList = "0"

	def eval( self, nt, ft, ht ) :
		if self.cond.eval( nt, ft, ht ) > 0 :
			self.tBody.eval( nt, ft, ht )
		else :
			self.fBody.eval( nt, ft, ht )

	def display( self, nt, ft, depth=0 ) :
		print "%sIF" % (tabstop*depth)
		self.cond.display( nt, ft, depth+1 )
		print "%sTHEN" % (tabstop*depth)
		self.tBody.display( nt, ft, depth+1 )
		print "%sELSE" % (tabstop*depth)
		self.fBody.display( nt, ft, depth+1 )


class WhileStmt( Stmt ) :

	def __init__( self, cond, body ) :
		self.cond = cond
		self.body = body
		self.isList = "0"

	def eval( self, nt, ft, ht ) :
		while self.cond.eval( nt, ft, ht ) > 0 :
			self.body.eval( nt, ft, ht )

	def display( self, nt, ft, depth=0 ) :
		print "%sWHILE" % (tabstop*depth)
		self.cond.display( nt, ft, depth+1 )
		print "%sDO" % (tabstop*depth)
		self.body.display( nt, ft, depth+1 )

#-------------------------------------------------------



class StmtList :
	'''builds/stores a list of Stmts'''

	def __init__( self ) :
		self.sl = []
		self.isList = "0"
	
	def insert( self, stmt ) :
		self.sl.insert( 0, stmt )
	
	def eval( self, nt, ft, ht ) :
		for s in self.sl :
			s.eval( nt, ft, ht )
		print "in StmtList"
	def display( self, nt, ft, depth=0 ) :
		print "%sSTMT LIST" % (tabstop*depth)
		for s in self.sl :
			s.display( nt, ft, depth+1 )


class Proc :
	'''stores a procedure (formal params, and the body)

	Note that, while each function gets its own environment, we decided not to
	allow side-effects, so, no access to any outer contexts.  Thus, nesting
	functions is legal, but no different than defining them all in the global
	environment.  Further, all calls are handled the same way, regardless of
	the calling environment (after the actual args are evaluated); the proc
	doesn't need/want/get an outside environment.'''

	def __init__( self, paramList, body ) :
		'''expects a list of formal parameters (variables, as strings), and a
		StmtList'''

		self.parList = paramList
		self.body = body
		self.isList = "0"

	def apply( self, nt, ft, ht, args ) :
		newContext = {}

		# sanity check, # of args
		if len( args ) is not len( self.parList ) :
			print "Param count does not match:"
			sys.exit( 1 )

		# bind parameters in new name table (the only things there right now)
		for i in range( len( args )) :
			newContext[ self.parList[i] ] = args[i].eval( nt, ft, ht )

		# KS Don't know what I was doin' here, but it's wrong 3/08
		# Thank you, Charles
		#[ newContext.__setitem__(p,a.eval( nt, ft ))
		#		for p in self.parList for a in args ]

		# evaluate the function body using the new name table and the old (only)
		# function table.  Note that the proc's return value is stored as
		# 'return in its nametable

		self.body.eval( newContext, ft, ht )
		if newContext.has_key( returnSymbol ) :
			return newContext[ returnSymbol ]
		else :
			print "Error:  no return value"
			sys.exit( 2 )
	
	def display( self, nt, ft, depth=0 ) :
		print "%sPROC %s :" % (tabstop*depth, str(self.parList))
		self.body.display( nt, ft, depth+1 )


class Program :
	
	def __init__( self, stmtList ) :
		self.stmtList = stmtList
		self.nameTable = {}
		self.funcTable = {}
		self.heapTable = Heap()
		
		
	
	
	def eval( self ) :
		self.stmtList.eval( self.nameTable, self.funcTable, self.heapTable )
	
	def dump( self ) :
		print "Dump of Symbol Table"
		print "Name Table"
		for k in self.nameTable :
			if(self.nameTable[k].isList == 0) :
				print "  %s -> %s " % ( str(k), str(self.nameTable[k].element) )
			else:
				print "  %s -> %s " % ( str(k), self.heapTable.listPrinter(self.nameTable[k]) )
		print "Function Table"
		for k in self.funcTable :
			print "  %s" % str(k)


	def display( self, depth=0 ) :
		print "%sPROGRAM :" % (tabstop*depth)
		self.stmtList.display( self.nameTable, self.funcTable )

